//#######################################################################
//# Author: huer0625
//# Created Time: 2011-3-9 18:33:41
//# File Name: String.h
//# Description: 
//#	下面实现了String类所有的功能；
//# 参考网站如下：
//# 1 http://users.cis.fiu.edu/~weiss/dsaa_c++/code/
//# 2 http://www.cplusplus.com/reference/String/String/
//#######################################################################
#ifndef STRING_H
#define STRING_H
#include "Iterator.h"
#include "Allocator.h"
#include <iostream>

#ifndef NULL
#define NULL ((void *)0)
#endif

class OutOfMemory
{
};

class StringIndexOutOfBound
{
};

class IteratorOutOfBound
{
};




class StringIterator : public Iterator<InputIteratorTag, char>
{
	char * p;
public:
	StringIterator() : p(0) {}
	StringIterator(char * x) : p(x) {}
	StringIterator(const StringIterator & it) : p(it.p) {}
	StringIterator& operator++() {++p; return *this;}	
	StringIterator operator++(int) {StringIterator tmp(*this); operator++(); return tmp;}
	bool operator==(const StringIterator & rhs) { return p == rhs.p;}
	bool operator!=(const StringIterator & rhs) { return !operator==(rhs);}
	char& operator*() { return *p;}
	StringIterator operator+(int d) {return p + d;}
	difference_type operator-(const StringIterator & it) 
	{ return p - it.p; }

	bool operator>(const StringIterator & rhs) { return p > rhs.p; }
	bool operator<=(const StringIterator & rhs) { return !operator>(rhs);}
	bool operator<(const StringIterator & rhs) { return p < rhs.p; }
	bool operator>=(const StringIterator &  rhs) { return !operator<(rhs); }
};

class StringReverseIterator : public Iterator<InputIteratorTag, char>
{
	char * p;
public:
	StringReverseIterator() : p(0) {}
	StringReverseIterator(char * x) : p(x) {}
	StringReverseIterator(const StringReverseIterator & it) : p(it.p) {}
	StringReverseIterator& operator++() {--p; return *this;}	
	StringReverseIterator operator++(int) {StringReverseIterator tmp(*this); operator++(); return tmp;}
	bool operator==(const StringReverseIterator & rhs) { return p == rhs.p;}
	bool operator!=(const StringReverseIterator & rhs) { return !operator==(rhs);}
	char& operator*() { return *p;}
	StringReverseIterator operator+(int d) {return p - d;}
	difference_type operator-(const StringReverseIterator & it) 
	{ return it.p - p; }

	bool operator>(const StringReverseIterator & rhs) { return p < rhs.p; }
	bool operator<=(const StringReverseIterator & rhs) { return !operator>(rhs);}
	bool operator<(const StringReverseIterator & rhs) { return p > rhs.p; }
	bool operator>=(const StringReverseIterator &  rhs) { return !operator<(rhs); }
};


class String 
{
	static Allocator<char>  Alloc;
	size_type len;
	char * buffer;
public:
	typedef Allocator<char>::size_type size_type;	
	typedef StringIterator iterator;
	typedef const StringIterator const_iterator;
	typedef StringReverseIterator reverse_iterator;
	typedef const StringReverseIterator const_reverse_iterator;
	static const size_t npos = -1;

	// 以下都是构造函数；
	String() : buffer(0), len(0) { }
	String(const char * s);
	String(const String& s);
	String(size_t n, char  c);
	String(const char * s, size_t n);
	String(const String & str, size_t pos, size_t n = String::npos);
	template<class InputIterator>
	String(InputIterator start, InputIterator end);
	~String() { delete [] buffer; }

	// String::begin();
	iterator begin() { return buffer; }
	const_iterator begin() const { return buffer; }

	// 返回C风格的字符串；
	const char * c_str() const { return (NULL == buffer ? "" : buffer); }

	// String::end();
	iterator end() { return buffer + strLength; }
	const_iterator end() const { return buffer + strLength; }


	// String::append
	String& append ( const String& str );
	String& append ( const String& str, size_t pos, size_t n );
	String& append ( const char* s, size_t n );
	String& append ( const char* s );
	String& append ( size_t n, char c );
	template<class InputIterator>
	String& append ( InputIterator first, InputIterator last );

	// String::operator=
	String& operator= ( const String& str);
	String& operator= ( const char* s);
	String& operator= ( char c );
	
	// String::operatro+=
	String& operator+= ( const String& str);
	String& operator+= ( const char* s);
	String& operator+= ( char c);

	// String::assign
	String& assign ( const String& str );
	String& assign ( const String& str, size_t pos, size_t n );
	String& assign ( const char* s, size_t n );
	String& assign ( const char* s );
	String& assign ( size_t n, char c );
	template<class InputIterator>
	String& assign ( InputIterator first, InputIterator last );
	

	// String::operator[]
	const char& operator[] ( size_t pos ) const { return buffer[pos]; }
	char& operator[] ( size_t pos ) { return buffer[pos]; }
	//String::at
	const char& at (size_t pos) const;
	      char& at (size_t pos);

	// Stirng::lenght()
	size_t length() const { return len; }
	// String::size
	size_t size() const {	return len; }
	// String::capacity
	size_t capacity () const { return len + 1; }
	// String::max_size
	size_t max_size() const { return npos; }


	// String::clear
	void clear(); 	

	// String::compare
	int compare ( const String& str ) const;
	int compare ( const char* s ) const;
	int compare ( size_t pos1, size_t n1, const String& str ) const;
	int compare ( size_t pos1, size_t n1, const char* s) const;
	int compare ( size_t pos1, size_t n1, const String& str, size_t pos2, size_t n2 ) const;
	int compare ( size_t pos1, size_t n1, const char* s, size_t n2) const;

	// String::copy
	size_t copy ( char* s, size_t n, size_t pos = 0) const;

	// String::data
	const char* data() const { return buffer; }

	// String::empty
	bool empty ( ) const { return (size_t)0 == len; }

	// String::erase
	String& erase ( size_t pos = 0, size_t n = npos );
	iterator erase ( iterator position );
	iterator erase ( iterator first, iterator last );
	
	// String::find
	size_t find ( const String& str, size_t pos = 0 ) const;
	size_t find ( const char* s, size_t pos, size_t n ) const;
	size_t find ( const char* s, size_t pos = 0 ) const;
	size_t find ( char c, size_t pos = 0 ) const;

	//String::find_first_not_of
	size_t find_first_not_of ( const String& str, size_t pos = 0 ) const;
	size_t find_first_not_of ( const char* s, size_t pos, size_t n ) const;
	size_t find_first_not_of ( const char* s, size_t pos = 0 ) const;
	size_t find_first_not_of ( char c, size_t pos = 0 ) const;

	//String::find_first_of
	size_t find_first_of ( const String& str, size_t pos = 0 ) const;
	size_t find_first_of ( const char* s, size_t pos, size_t n ) const;
	size_t find_first_of ( const char* s, size_t pos = 0 ) const;
	size_t find_first_of ( char c, size_t pos = 0 ) const;

	//String::find_last_not_of
	size_t find_last_not_of ( const String& str, size_t pos = npos ) const;
	size_t find_last_not_of ( const char* s, size_t pos, size_t n ) const;
	size_t find_last_not_of ( const char* s, size_t pos = npos ) const;
	size_t find_last_not_of ( char c, size_t pos = npos ) const;

	//String::find_last_of
	size_t find_last_of ( const String& str, size_t pos = npos ) const;
	size_t find_last_of ( const char* s, size_t pos, size_t n ) const;
	size_t find_last_of ( const char* s, size_t pos = npos ) const;
	size_t find_last_of ( char c, size_t pos = npos ) const;

	//String::insert
	String& insert ( size_t pos1, const String& str );
	String& insert ( size_t pos1, const String& str, size_t pos2, size_t n );
	String& insert ( size_t pos1, const char* s, size_t n);
	String& insert ( size_t pos1, const char* s );
	String& insert ( size_t pos1, size_t n, char c );
	iterator insert ( iterator p, char c );
	void insert ( iterator p, size_t n, char c );
	//template<class InputIterator>
	template<class InputIterator>
	void insert ( iterator p, InputIterator first, InputIterator last );

	// String::push_back
	void push_back ( char c );

	//String::replace
	String& replace ( size_t pos1, size_t n1,   const String& str );
	String& replace ( iterator i1, iterator i2, const String& str );
	String& replace ( size_t pos1, size_t n1, const String& str, size_t pos2, size_t n2 );
	String& replace ( size_t pos1, size_t n1,   const char* s, size_t n2 );
	String& replace ( iterator i1, iterator i2, const char* s, size_t n2 );
	String& replace ( size_t pos1, size_t n1,   const char* s );
	String& replace ( iterator i1, iterator i2, const char* s );
	String& replace ( size_t pos1, size_t n1,   size_t n2, char c );
	String& replace ( iterator i1, iterator i2, size_t n2, char c );
	//template<class InputIterator>
	template<class InputIterator>
	String& replace ( iterator i1, iterator i2, InputIterator j1, InputIterator j2 );

	// String::reserve
	void reserve ( size_t res_arg=0 );

	// String::swap
	void swap ( String& str );
	//String::substr
	String substr ( size_t pos = 0, size_t n = npos ) const;

	// String::rbegin
	      reverse_iterator rbegin();
	const_reverse_iterator rbegin() const;

	// String::rend
	      reverse_iterator rend();
	const_reverse_iterator rend() const;



	// friend function
	friend std::ostream & operator << (std::ostream & os,const String &str);
	
private:
	size_t doFind(const char * s1, const char * s2, size_t pos) const;	
	size_t doFindFirstNotOf(const char * s1, const char * s2, size_t pos ) const;	
	size_t doFindFirstOf(const char * s1, const char * s2, size_t pos ) const;	
	size_t doFindLastNotOf(const char * s1, const char * s2, size_t pos ) const;	
	size_t doFindLastOf(const char * s1, const char * s2, size_t pos ) const;
	size_t strlen(const char * str) const
	{
		size_t ret(0);
		
		while(*str++)
			ret++;
		return ret;
	}
	char * strcpy(char *dest, const char * src) const
	{
		char * p = dest;
		while((*p++ = *src++))
			;
		return dest;
	}
	char * strncpy(char *dest, const char * src, size_t n) const
	{
		char *p = dest;
		size_t cnt = 0;
		while((cnt++ < n) && (*p++ = *src++))
			;
		*p = '\0';
		return dest;
	}
	int strcmp(const char * s1, const char * s2) const
	{
		while (*s1 && *s2 && *s1 == *s2)
		{
			s1++;
			s2++;
		}

		return (*s1 - *s2);
	}
};	

std::istream& getline ( std::istream& is, String& str, char delim );
std::istream& getline ( std::istream& is, String& str );

String operator+ (const String& lhs, const String& rhs);
String operator+ (const char* lhs, const String& rhs);
String operator+ (char lhs, const String& rhs);
String operator+ (const String& lhs, const char* rhs);
String operator+ (const String& lhs, char rhs);

// comparison operators function
bool operator== ( const String& lhs, const String& rhs );
bool operator== ( const char* lhs, const String& rhs );
bool operator== ( const String& lhs, const char* rhs );

bool operator!= ( const String& lhs, const String& rhs );
bool operator!= ( const char* lhs, const String& rhs );
bool operator!= ( const String& lhs, const char* rhs );

bool operator< ( const String& lhs, const String& rhs );
bool operator< ( const char* lhs, const String& rhs );
bool operator< ( const String& lhs, const char* rhs );

bool operator> ( const String& lhs, const String& rhs );
bool operator> ( const char* lhs, const String& rhs );
bool operator> ( const String& lhs, const char* rhs );

bool operator<= ( const String& lhs, const String& rhs );
bool operator<= ( const char* lhs, const String& rhs );
bool operator<= ( const String& lhs, const char* rhs );

bool operator>= ( const String& lhs, const String& rhs );
bool operator>= ( const char* lhs, const String& rhs );
bool operator>= ( const String& lhs, const char* rhs );


#endif  /* STRING_H */
